package Leetcode.图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @Author: kirito
 * @Date: 2024/9/16 16:08
 * @Description:
 * 给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间
 * 有一条需要 lengthi 单位时间通过的无向边。
 *
 * 同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。
 *
 * 注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。
 *
 * 请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，
 * 那么 answer[i] 为 -1 。
 *
 * 输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]
 *
 * 输出：[0,-1,4]
 */

public class 访问消失节点的最少时间 {
    /**
     *先不管 disappear，用 Dijkstra 算法模板求出 dis 数组，然后把其中 dis[i]≥disappear[i] 的 dis[i] 改成 −1。这个做法是否正确？
     *
     * 答：这个做法是错的。考虑这样的数据：离节点 0 近的节点 x，其 disappear[x] 很小；离节点 0 远的节点 y，其 disappear[y] 很大。
     * 由于 disappear[x] 很小，我们无法通过节点 x，所以远处的节点 y 实际上也无法到达。但错误做法会因为 dis[y]<disappear[y]，
     * 误认为节点 y 可以到达，最终返回错误的答案。
     *
     * 对于本题，answer 几乎就是 dis 数组。只需要在 Dijkstra 算法的过程中，添加一个判断：
     *
     * 在更新最短路之前，如果最短路长度 ≥disappear[i]，说明无法及时到达节点 i，不更新。
     *
     */
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        // 创建一个图，使用邻接表表示，每个节点的邻居列表是一个ArrayList
        List<int[]>[] graph = new ArrayList[n];
        // 初始化图中的每个节点对应的邻居列表
        Arrays.setAll(graph, item -> new ArrayList<>());
        // 遍历所有边，构建无向图
        for (int[] edge : edges) {
            int x = edge[0]; // 边的起点
            int y = edge[1]; // 边的终点
            int weight = edge[2]; // 边的权重
            // 添加双向边
            graph[x].add(new int[]{y, weight});
            graph[y].add(new int[]{x, weight});
        }

        // 初始化距离数组，所有节点的距离设置为-1，表示未访问
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        // 起点距离为0
        dist[0] = 0;
        // 创建优先队列，用于Dijkstra算法，按照距离排序
        PriorityQueue<int[]> priQue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        // 起点入队
        priQue.offer(new int[]{0, 0});
        // 当优先队列不为空时，执行Dijkstra算法
        while (!priQue.isEmpty()) {
            // 取出队列中距离最小的节点
            int[] temp = priQue.poll();
            int dx = temp[0]; // 当前节点的距离
            int x = temp[1]; // 当前节点的编号
            // 如果当前节点的距离大于记录的距离，跳过
            if (dx > dist[x]) {
                continue;
            }
            // 遍历当前节点的所有邻居
            for (int[] e : graph[x]) {
                int y = e[0]; // 邻居节点的编号
                int newDis = dx + e[1]; // 计算新的距离
                // 如果新距离小于消失时间且小于记录的距离，更新距离并加入队列
                if (newDis < disappear[y] && (dist[y] < 0 || newDis < dist[y])) {
                    dist[y] = newDis; // 更新距离
                    priQue.offer(new int[]{newDis, y}); // 新的距离和节点入队
                }
            }
        }
        // 返回最终的距离数组
        return dist;
    }

}
